As software gets more complex, so does testing the software to ensure that it works properly. As a result, software engineers have devised testing tools that facilitate the process of testing software.
Typically, a testing tool automatically generates sample inputs, known as test cases, for a program and then executes the program on each of the test cases, thereby enabling a human tester to compare the results of these test cases with the desired behavior. Testing tools that generate sample inputs based on an analysis of the source code of a program are known as whitebox tools, while testing tools that generate sample inputs without considering source code are known as blackbox tools.
Whitebox testing tools typically can be categorized into four classes. Random testing tools randomly generate test cases based on source code. Path-oriented testing tools identify a set of paths through the source code and generate appropriate test cases to cover the paths. Goal-oriented testing tools identify test cases that satisfy a selected goal (e.g., coverage of a particular statement in the source code, etc.), irrespective of the path that is traversed. Intelligent testing tools analyze the source code and identify potential error-prone sections of the program (e.g., a block of code that uses pointers extensively, etc.).
Path-oriented testing tools are advantageous because they can ensure that every line of code in a source program is executed by at least one test case. Path-oriented testing tools work by constructing a control-flow graph of a source program. A control-flow graph is a directed graph (N, A, s, X) where N is a set of nodes; A⊂N×N is a set of arcs; SεN is a unique starting node; and a proper subset X⊂N of one or more ending nodes. Each node corresponds to a program block, which is a list of one or more program statements that are executed sequentially in deterministic fashion, and each arc corresponds to a control transfer from one program block to another. If more than one outgoing arc leaves a node, then each outgoing arc is labeled with a logical expression such that exactly one of the logical expressions is true for any given instantiation of variables. For example, three outgoing arcs from a node might be labeled i<x, i=x and i>x, respectively.
FIG. 1 depicts the source code of an illustrative program, and control-flow graph 100 that corresponds to the program. Each node 101, 102, . . . , 110 corresponds to one or more lines of code of the program, as indicated by the label of the node (e.g., node 101 corresponds to lines 1 through 5, etc.). The starting node, in this case node 101, is indicated by a double ellipse, and the single ending node, in this case node 110, is indicated by a triple ellipse. A labeled arc from a first node to a second node indicates the corresponding condition of the program that is necessary for a transition from the first node to the second node.
After constructing a control-flow graph, a path-oriented tool generates a set of paths from the starting node s to the ending node e such that all nodes in the control-flow graph are covered. A number of different techniques are known in the art to generate a test case for each generated path by assigning values to input variables accordingly. The source program can then be tested by executing the program for each test case and comparing the results with the expected behavior of the program.